The present invention relates to digital filtering, and more particularly, to multi-rate sub-band analysis and synthesis.
Multirate filter banks are used to decompose a signal into multiple sub-bands. The subband coefficients are calculated through successive iterations of the convolution and decimation operators. Various subband decompositions can be obtained by varying the decomposition tree structure; for example, FIGS. 2a–2c illustrate some tree structures: FIG. 2a shows a two-channel full tree of two levels, FIG. 2b has a combination of two-channel, three-channel and four-channel branchings, and FIG. 2c is a one-dimensional half-band analysis tree as used in a discrete wavelet transform: h0 is the lowpass (scaling function) analysis filter, h1 the highpass (wavelet) analysis filter, and ↓2 represents decimation (subsampling) by a factor of 2. The input signal s(t) is transformed into wavelet coefficients S(j,w). For two-dimensional images, the wavelet decomposition may use a one-dimensional half-band decomposition in each dimension to yield a four-channel decomposition at each level; the lowpass-lowpass channel is decomposed for the next level. Generally, an M-channel filter bank should allow the M outputs to each be decimated by a factor of M, indicated by ↓M, without loss of information due to the effective partitioning of the spectrum into M portions by the filter bank.
Reconstruction of the original signal from the subband coefficients is possible if the proper synthesis filters are chosen, and the synthesis tree structure mirrors the analysis tree structure. FIG. 3a shows the simplest situation of decomposition of input s[n] into two subband coefficients, y1[n] and y2[n], by analysis filters h0 and h1 followed by reconstruction of (an approximate) ŝ[n] from the two subband coefficients with synthesis filters g0 and g1. FIG. 3b illustrates the same analysis and reconstruction with the inclusion of decimation by a factor of two, denoted ↓2, in the decomposition plus compensating interpolation by 2, denoted by ↑2, preceding the synthesis filters, g0 and g1, in the reconstruction. As an example, the JPEG2000 standard reversible 1 D transformation includes wavelet analysis filters h0 for lowpass and h1 for highpass with h0[0]=−⅛, h0[1]=¼, h0[2]=¾, h0[3]=¼, h0[4]=−⅛, and h1[0]=−½, h1[1]=1, h1[2]=−½. The synthesis filters, g0 and g1, are simply phase shifts by π of the h1 and h0, respectively. That is, g0[n]=(−1)n+1 h1[n] and g1[n]=(−1)n h0[n].
More generally, the transformation of an input sequence x[n] by analysis filtering using a causal filter (kernel) hana[n] followed by decimation by an integral factor M to yield coefficients in a subband has two steps:
      z    ⁡          (      m      )        =            ∑              k        <        m              ⁢                            h          ana                ⁡                  [                      m            -            k                    ]                    ×              [        k        ]            ⁢                          ⁢              (                  convolution          ⁢                                          ⁢          by          ⁢                                          ⁢                                    h              ana                        ⁡                          [              n              ]                                      )            y[n]=z[nM]  (decimation by M)
These combine into a single convolution:
      y    ⁡          [      n      ]        =            ∑              k        ≤        nM              ⁢                  ⁢                            h          ana                ⁡                  [                      nM            -            k                    ]                    ×              [        k        ]            Typically, there would be M subbands, each with its own analysis filter.
Analogously, the general reconstruction has two steps: interpolation by an integral factor L followed by synthesis filtering with hsyn[n]:
                              z          ⁡                      [            m            ]                          =                  0          ⁢                                          ⁢          when          ⁢                                          ⁢                      m            /            L                    ⁢                                          ⁢          is          ⁢                                          ⁢          not          ⁢                                          ⁢          an          ⁢                                          ⁢          integer                                        =                              x            ⁡                          [                              m                /                L                            ]                                ⁢                                          ⁢          when          ⁢                                          ⁢                      m            /            L                    ⁢                                          ⁢          is          ⁢                                          ⁢          an          ⁢                                          ⁢          integer          ⁢                                          ⁢                      (                          interpolation              ⁢                                                          ⁢              by              ⁢                                                          ⁢              L                        )                                                            y          ⁡                      [            n            ]                          =                              ∑                          m              ≤              n                                ⁢                                          ⁢                                                    h                syn                            ⁡                              [                                  n                  -                  m                                ]                                      ⁢                                                  ⁢                          z              ⁡                              [                m                ]                                      ⁢                                                  ⁢                          (                              convolution                ⁢                                                                  ⁢                by                ⁢                                                                  ⁢                                  h                  ⁡                                      [                    n                    ]                                                              )                                                              =                              ∑                          k              ≤                              floor                ⁡                                  (                                      n                    /                    L                                    )                                                              ⁢                                                    h                syn                            ⁡                              [                                  n                  -                                      k                    ⁢                                                                                  ⁢                    L                                                  ]                                      ⁢                                                  ⁢                          z              ⁡                              [                                  k                  ⁢                                                                          ⁢                  L                                ]                                                                            =                              ∑                          k              ≤                              floor                ⁡                                  (                                      n                    /                    L                                    )                                                              ⁢                                                    h                syn                            ⁡                              [                                  n                  -                                      k                    ⁢                                                                                  ⁢                    L                                                  ]                                      ⁢                                                  ⁢                          x              ⁡                              [                k                ]                                                        Note that the summation limit floor(n/L) is largest integer not smaller than n/L; that is, the integer part of n/L. Again, with L subbands, there would be L different synthesis filters and the results of interpolation and filtering of each subband would be combined to form the final synthesized signal.
The reconstruction process requires use of all of the subband coefficients. However, in some applications, due to memory and computational constraints, it is desirable to reconstruct only select regions of the signal. For this to be done efficiently and effectively, a method for determining which subband coefficients are necessary for the reconstruction of an arbitrary data region of the synthesized signal is needed.
Conversely, in analysis applications, the original signal may be modified in certain regions. Instead of re-encoding the entire signal, it would be desirable to encode only the modified portion of the signal and replace the appropriate subband coefficients from the old analysis with the coefficients from the new analysis. A method for determining which subband coefficients refer to which parts of the input signal is required.